package _01_动态数组;

import java.util.HashMap;
import java.util.Map;

public class _149_直线上最多的点数 {

    public static void main(String[] args) {

        /*int[][] points = new int[][]{
                {1, 1},
                {3, 2},
                {5, 3},
                {4, 1},
                {2, 3},
                {1, 4},
        };
*/
        int[][] points = new int[][]{
                {1, 1},
                {2, 2},
                {3, 3},
        };

       /* int[][] points = new int[][]{
                {0, 0},
                {1, -1},
                {1, 1}
        };*/

        _149_直线上最多的点数 v = new _149_直线上最多的点数();

        System.out.println(v.maxPoints(points));

    }


    // 枚举一个点对应的其他点，如果斜率相同，那么就在同一条直线上。并且求出最大值
    // o(n^2)复杂度
    public int maxPoints(int[][] points) {
        int max = 1;
        for (int i = 0; i < points.length; i++) {
            int curX = points[i][0];
            int curY = points[i][1];
            // 当前遍历的点，斜率对应的元素个数
            Map<Double, Integer> container = new HashMap<>();
            for (int j = 0; j < points.length; j++) {
                if (i == j) continue;
                int compareX = points[j][0];
                int compareY = points[j][1];
                double rake;
                if (compareY == curY) {
                    rake = Double.MAX_VALUE;
                    // 斜率无穷大
                } else if (compareX == curX) {
                    rake = 0.0;
                    // 斜率为0
                } else {
                    // 斜率为正常情况
                    rake = (curX - compareX) / (double) (curY - compareY);
                }
                container.put(rake, container.getOrDefault(rake, 1) + 1);
            }
            // 找出map中最大斜率
            for (Integer value : container.values()) {
                max = Math.max(value, max);
            }
        }
        return max;
    }

}
